package number_08_13;

import java.util.*;

public class Solution {
    private int res = 0;
    public int pileBox(int[][] box) {
        if (box == null || box.length == 0) {
            return 0;
        }
        if (box.length == 1) {
            return box[0][2];
        }
        List<int[]> boxList = new ArrayList<>();

        for (int i = 0; i < box.length; i++) {
            boxList.add(box[i]);
        }
        Collections.sort(boxList, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] < o2[0] || o1[0] > o2[0]) {
                    return o1[0] - o2[0];
                }
                if (o1[1] < o2[1] || o1[1] > o2[1]) {
                    return o1[1] - o2[1];
                }
                return o1[2] - o2[2];
            }
        });

        for (int i = boxList.size() - 1; i >= 0; i--) {
            countPileBox(boxList, i - 1, boxList.get(i), boxList.get(i)[2]);
        }

        return res;
    }

    private void countPileBox(List<int[]> boxList, int index, int[] box, int height) {
        for (int i = index; i >= 0; i--) {
            int[] tmpBox = boxList.get(i);
            if (tmpBox[0] < box[0] && tmpBox[1] < box[1] && tmpBox[2] < box[2]) {
                countPileBox(boxList, i - 1, tmpBox, height + tmpBox[2]);
            }
        }
        res = Math.max(res, height);
    }

    //dp;
    public int pileBox1(int[][] box) {
        Arrays.sort(box, (a, b) -> {
            return a[0] == b[0] ? a[1] == b[1] ? b[2] - a[2] : b[1] - a[1] : a[0] - b[0];
        });

        int[] dp = new int[box.length];
        int res = dp[0];
        for (int i = 0; i < box.length; i++) {
            int maxVal = 0, baseDepth = box[i][1], baseHeight = box[i][2];
            for (int j = 0; j < i; j++) {
                if (baseDepth > box[j][1] && baseHeight > box[j][2]) {
                    maxVal = Math.max(maxVal, dp[j]);
                }
            }
            dp[i] = maxVal + baseHeight;
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    public static void main(String[] args) {
        new Solution().pileBox1(new int[][]{{1,1,1}, {1,1,2}, {2,2,3}, {4,4,4}});
    }


}
